package cn.myworld.algorithm.linear;

import cn.myworld.algorithm.common.BaseList;

import java.util.Iterator;

/**
 * 单向链表
 * @param <T>
 */
public class LinkList<T> implements BaseList<T> {

    // 记录头结点
    private Node head;
    // 记录链表的长度
    private int N;

    // 节点类
    private class Node {
        // 储存数据
        T data;
        // 下一个节点
        Node next;
        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    public LinkList() {
        // 初始化头结点
        this.head = new Node(null, null);
        // 初始化元素个数
        this.N = 0;
    }

    @Override
    public void clear() {
        head.next = null;
        N = 0;
    }

    @Override
    public boolean isEmpty() {
        return N == 0;
    }

    @Override
    public int length() {
        return N;
    }

    @Override
    public T get(int i) {
        // 通过循环，从头结点往后找，依次找i次
         Node n = head.next;
         for (int index = 0; index < i; index++) {
             n = n.next;
         }
        return n.data;
    }

    @Override
    public void insert(T e) {
        // 找到当前最后一个节点
        Node n = head;
        while (n.next != null) {
            n = n.next;
        }
        // 创建新节点，保存元素e
        Node newNode = new Node(e, null);
        // 让最后一个节点指向新节点
        n.next = newNode;
        // 元素个数+1
        N++;
    }

    @Override
    public void insert(int i, T e) {
        // 找到i位置前一个节点
        Node pre = head;
        for (int index = 0; index < i; index++) {
            pre = pre.next;
        }
        // 找到i位置节点
        Node cur = pre.next;
        // 创建新节点，指向原来i位置节点
        Node newNode = new Node(e, cur);
        // 原来i位置前一个节点指向新节点
        pre.next = newNode;
        // 元素个数+1
        N++;
    }

    @Override
    public T remove(int i) {
        // 找到i位置前一个节点
        Node pre = head;
        for (int index = 0; index < i; index++) {
            pre = pre.next;
        }
        // 找到i位置节点
        Node cur = pre.next;
        // 找到i位置下一个节点
        Node next = cur.next;
        // 前一个节点指向下一个节点
        pre.next = next;
        // 元素个数-1
        N--;
        return cur.data;
    }

    @Override
    public int indexOf(T e) {
        // 从头节点开始一次找到每一个节点，取出data，和e比较，如果相同则找到
        Node n = head;
        for (int index = 0; n.next != null; index++) {
            n = n.next;
            if (n.data.equals(e)) {
                return index;
            }
        }
        return -1;
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkList.LIterator();
    }

    private class LIterator implements Iterator<T> {
        private Node n;
        public LIterator() {
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public T next() {
            n = n.next;
            return n.data;
        }
    }

    // 反转整个链表
    public void reverse() {

        // 判断当前链表是否为空
        if (isEmpty()) return;

        reverse(head.next);

    }

    // 反转指定的节点，并把反转后的节点返回
    public Node reverse(Node curr) {
        if (curr.next == null) {
            head.next = curr;
            return curr;
        }
        // 递归反转当前节点curr的下一个节点，返回值是链表反转后当前节点的上一个节点
        Node pre = reverse(curr.next);
        // 让返回的节点的下一个节点变为当前节点curr
        pre.next = curr;
        // 把当前节点的下一个节点变为null
        curr.next = null;

        return curr;
    }
}
